Analizator rekurzivnim spustom

Analizator rekurzivnim spustom je analizator naniže napravljen od skupa višeznačno-rekurzivnih procedura (ili nerekurzivnih ekvivalenata) gde svaka od procedura najčešće implementira jedno od pravila gramatike. Tako struktura rezultujućeg programa najbliže preslikava gramatiku koja je prepoznata.

Preduvidni analizator je analizator rekurzivnim spustom koji ne zahteva vraćanje unazad. Preduvidna analiza je moguća jedino za klase LL(k) gramatika, tj. onih kontekstno slobodnih gramatika za koje postoji neki pozitivan ceo broj k koji dozvoljava analizatoru da odluči koje pravilo gramatike da primeni ispitujući prvih k tokena na ulazu. (LL(k) gramatike prema tome isključuju sve višeznačne gramatike, kao i sve gramatike koje sadrže levu rekurziju. Svaka kontekstno slobodna gramatika se može transformisati u ekvivalentnu gramatiku bez leve rekurzije, iako uklanjanje leve rekurzije neće uvek dovesti do LL(k) gramatike.) Preduvidni analizator završava rad u linearnom vremenu.

Rekurzivni spust sa podrškom je tehnika kojom se određuje koje pravilo će se primeniti tako što isprobava sva pravila, redom. Rekurzivni spust sa podrškom nije ograničen na LL(k) gramatike, ali ne garantuje da će završiti osim ako gramatika nije LL(k). Čak i kada uspešno završe, analizatori koji koriste rekurzivni spust sa podrškom mogu da zahtevaju eksponencijalno vreme za rad.

Iako su preduvidni analizatori široko rasprostranjeni, programeri često radije prave LR ili LALR analizatore pomoću generatora analizatora bez transformacije gramatike u LL(k) formu.

Neki autori definišu analizatore rekurzivnim spustom kao preduvidne analizatore. Drugi taj termin koriste šire, te uključuju rekurzivni spust sa podrškom.^{[тражи се извор]}